package Solutions;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Classname WordExit
 * @Description TODO
 * @Date 2021/6/16 17:05
 * @Created by ASUS
 */
public class WordExit {

    public boolean exist_(char[][] board, String word) {
        if (board.length == 0) return false;
        if (board.length * board[0].length < word.length()) return false;
        char[] chars = word.toCharArray();
        int[] location = new int[2];
        int idx = 0, wordLen = word.length() - 1;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == chars[idx]) {
                    if (idx == wordLen) return true;
                    if (closeTo(location, i, j)) {
                        location[0] = i;
                        location[1] = j;
                        idx++;
                    } else return false;
                }
            }
        }
        return false;
    }

    private boolean closeTo(int[] location, int i, int j) {
        int x =location[0],y=location[1];
        if (i == x - 1 && j == y) return true;
        if (i == x && j == y - 1) return true;
        if (i == x && j == y + 1) return true;
        if (i == x + 1 && j == y) return true;
        if (i == x && j == y) return true;
        return false;
    }

    public int[] MySort (int[] arr) {
        // write code here
        int length = arr.length;
        if (length<=1) return arr;
        int index = 0, max = arr[0], tmp;
        while(length>0){
            max = arr[0];
            for(int i=0;i<length;i++){
                if (arr[i] > max) {
                    index = i;
                    max = arr[i];
                }
            }
            tmp = arr[length-1];
            arr[length-1]=max;
            arr[index] = tmp;
            index = 0;
            length--;
        }
        return arr;
    }

    public static void main(String[] args) {
        char[][] b = {
                {'A','B','C','E'},
                {'S','F','C','S'},
                {'A','D','E','E'}
        };
        int[] ints = new int[]{5,2,3,1,4};
        System.out.println(Arrays.toString(new WordExit().MySort(ints)));
        System.out.println(new WordExit().exist(b, "ABCCED"));
    }

    /***
     * 执行结果：
     * 通过
     * 显示详情
     *
     * 添加备注
     * 执行用时：10 ms, 在所有 Java 提交中击败了14.52% 的用户
     * 内存消耗：38.9 MB, 在所有 Java 提交中击败了98.84% 的用户
     */
    public boolean exist(char[][] board, String word) {
        if (board.length == 0) return false;
        if (board.length * board[0].length < word.length()) return false;
        int[][] visited = new int[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    visited[i][j] = 1;
                    if (dfs(word, 1, board, i, j, visited)) return true;
                    visited[i][j] = 0;
                }
            }
        }
        return false;
    }

    private boolean dfs(String word, int idx, char[][] board, int x, int y, int[][] visited) {
        if (idx == word.length()) return true;
        List<int[]> locs = getNext(x, y, visited);
        for (int[] loc : locs) {
            int r = loc[0];
            int c = loc[1];
            if (board[r][c] == word.charAt(idx)) {
                visited[r][c] = 1;
                if (dfs(word, idx + 1, board, r, c, visited)) return true;
                visited[r][c] = 0;
            }
        }
        return false;
    }

    private List<int[]> getNext(int x, int y, int[][] visited) {
        List<int[]> res = new ArrayList<>();

        if (x - 1 >= 0 && visited[x-1][y] == 0) {
            res.add(new int[]{x-1, y});
        }
        if (x + 1 < visited.length && visited[x+1][y] == 0) {
            res.add(new int[]{x+1, y});
        }
        if (y - 1 >= 0 && visited[x][y-1] == 0) {
            res.add(new int[]{x, y-1});
        }
        if (y + 1 < visited[0].length && visited[x][y+1] == 0) {
            res.add(new int[]{x, y+1});
        }

        return res;
    }

}
